1. Field of the Invention
The invention relates generally to equalization and decoding in communication systems, and in particular, to sequence estimation techniques with reduced complexity.
2. Discussion of the Prior Art
A limiting factor in the performance of digital communication systems which are designed to transmit digital data over a time-dispersive channel is intersymbol interference (ISI). FIG. 1 shows the block diagram for a conventional receiver 100 in a channel environment associated with, for example, the Gigabit Ethernet 1000 Base-T standard. As shown in FIG. 1, the receiver 100 includes an analog-to-digital (A/D) converter 110 for converting the received analog signal to a digital signal. The digitized data is then processed by a feed forward equalizer (FFE) 120; an echo canceller 130 and a crosstalk canceller 140. Generally, the feed forward equalizer (FFE) 120 makes the channel impulse causal, and additionally whitens the noise. In addition, the echo canceller 130 removes echo from the received signal and the crosstalk canceller 140 removes the crosstalk, as is well known in the art. The equalizer/decoder 150 performs data detection, for example, using maximum likelihood sequence estimation (MLSE), to produce output symbols or bits.
It is well known that MSLE is the optimum method for the recovery of a data sequence in the presence of ISI and additive white Gaussian noise (AWGN). For a more detailed discussion of a maximum likelihood sequence estimation (MLSE), see G. D. Forney Jr., xe2x80x9cMaximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference,xe2x80x9d IEEE Trans. Inform. Theory, vol. IT-18, pp. 363-378, May 1972, incorporated by reference herein.
The Viterbi Algorithm is a computationally efficient implementation of MLSE, however, it requires an excessive amount of computing power for most practical channels found in broadband communication systems. For a more detailed discussion of the Viterbi algorithm, see G. D. Forney, Jr. xe2x80x9cThe Viterbi Algorithm,xe2x80x9d Proc. IEEE, vol. 61, pp. 268-278, March 1973. Several sub-optimal modifications to the Viterbi algorithm have been introduced to reduce the computational complexity of the Viterbi algorithm. One such technique is reduced state sequence estimation (RSSE). Referring to FIG. 1, block 150, the equalizer/decoder may be implemented as an RSSE circuit. Two special cases of RSSE are Decision-feedback sequence estimation (DFSE), and parallel decision feedback decoding (PDFD). DFSE employs a trellis that takes into account only the first K of the L channel coefficients {fi}, 1xe2x89xa6ixe2x89xa6L, where L is the channel memory. PDFD is a special case of DFSE when K=0, where the reduced trellis becomes the TCM code trellis and decision feedback equalization is performed for each code state based on its survivor history. For a discussion of reduced state sequence estimation (RSSE) techniques and for the special cases (i.e., DFSE and PDFD), see, for example, P. R. Chevillat and E. Eleftheriou, xe2x80x9cDecoding of Trellis-Encoded Signals in the Presence of Intersymbol Interference and Noisexe2x80x9d, IEEE Trans. Commun., vol. 37, 669-76, (July 1989) and M. V. Eyuboglu and S. U. H. Qureshi, xe2x80x9cReduced-State Sequence Estimation For Coded Modulation On Intersymbol Interference Channelsxe2x80x9d, IEEE JSAC, vol. 7, 989-95 (August 1989), each incorporated by reference herein. RSSE is well suited for implementation in dedicated hardware due to its high parallelism, unlike other reduced complexity sequence estimation techniques such as the M-algorithm. For a discussion of M-algorithms (MA), see, for example, N. Seshadri and J. B. Anderson, xe2x80x9cDecoding of Severely Filtered Modulation codes Using the (M,L) Algorithmxe2x80x9d, IEEE JSAC, vol. 7, 1006-1016 (August 1989), incorporated by reference herein. Although RSSE has been proposed as a means to reduce the computational complexity of MLSE, the hardware cost of RSSE can still be very high.
FIG. 2 is an implementation of an RSSE equalizer/decoder which attempts to reduce the intersymbol interference associated with all channel coefficients, {fi}, 1xe2x89xa6ixe2x89xa6L, of the channel impulse response with memory L. The R decision feedback cells 209 of FIG. 2 compute R ISI estimates in the decision feedback unit (DFU) 208 based on the survivor symbols from the corresponding survivor path cells 207 of FIG. 2 in the survivor memory unit (SMU) 206. These estimates are fed into the branch metric unit (BMU) 202 in which each branch metric cell 203 of FIG. 2 computes the b metrics for the transitions emanating from the corresponding state. In the add/compare select unit (ACSU) 204 each add/compare select cell selects the best survivor path among all paths entering the state.
While RSSE reduces the complexity of MLSE, its hardware costs can still be very high in practical applications. To reduce the hardware costs of RSSE, it has been proposed to account only for the ISI introduced by the first U taps of the channel impulse response, {fi}, 1xe2x89xa6ixe2x89xa6U with an RSSE structure 302, as shown in FIG. 3, and cancel the remaining ISI with a simple equalizer structure 304. Referring again to block 150 of FIG. 1, it was previously stated that block 150 could be implemented as structure 200 of FIG. 2. Structure 300 of FIG. 3 represents another possible structure to implement block 150 to reduce the complexity of MLSE.
FIG. 4 is an illustration of the RSSE structure 302 of FIG. 3. In the decision feedback unit (DFU) 408 each decision feedback cell 409 takes care of the ISI introduced by the first U channel coefficients, {f}, 1xe2x89xa6ixe2x89xa6U, where the number U is predetermined. The ISI from only the first U channel coefficients are considered in the RSSE apparatus 302 of FIG. 3 based on an assumption that the channel impulse response which is seen by the equalizer/decoder (See block 150 of FIG. 1) is concentrated in the first U taps, as shown by the graph of signal energy v. coefficient index, i, in FIG. 5a. Further, Block 304 of FIG. 3 reduces the intersymbol interference from other than the first U taps, {fi}, U+1xe2x89xa6ixe2x89xa6L. This assumption is often valid for a minimum phase channel, however, in general the channel impulse response may be concentrated in taps other than the first U taps (e.g. Gigabit Ethernet over copper), or components in the tail of the channel impulse response may be significant. Furthermore, the distribution of the channel impulse response may change over time. As such, the channel energy will be concentrated in different taps as a function of time. FIG. 5b illustrates a channel impulse response graph with significant channel coefficients in the tail. In these cases the reduced complexity RSSE equalizer/decoder 300 of FIG. 3, would exhibit significantly inferior performance. Thus, there is a need for a low computationally complex RSSE equalizer/decoder that exhibits acceptable performance in a wide variety of channel impulse responses and which is adaptively reconfigurable in response to changing channel environments and does not change the number of states as disclosed in the prior art.
The present invention provides an apparatus and method for reducing the computational complexity of the RSSE technique by reducing the intersymbol interference caused by significant channel coefficients with a tap selectable TS-RSSE (i.e., high complexity equalization and decoding algorithm). The more significant channel coefficients are adaptively selected in response to changes in the channel impulse response. Further, the intersymbol interference caused by the less significant channel coefficients is processed by a tap selectable decision feedback prefilter TS-DFP (i.e., a low complexity equalization algorithm). Referring again to FIG. 1, which is an illustration of the channel environment associated with, for example, the Gigabit Ethernet 1000 Base-T standard, the equalizer/decoder of the present invention could be used to implement the block 150. Utilizing the equalizer/decoder of the present invention to implement block 150 is advantageous because of its reduced complexity and also because of its improved adaptivity to a changing channel impulse response as compared to the prior art.
The present invention is based on the observation that for a communication channel having a channel memory L and comprising L+1 channel coefficients, {fi}, 0xe2x89xa6ixe2x89xa6L, only a subset of the L channel coefficients associated with the memory, {fi}, 1xe2x89xa6ixe2x89xa6L, will contribute most significantly to the intersymbol interference caused by the channel. Prior art approaches have assumed the most significant coefficients associated with the channel memory to be concentrated in the initial taps of the channel impulse response {fi}, 1xe2x89xa6ixe2x89xa6U. However, this assumption does not hold true in some applications like Gigabit ethernet over copper or broadband wireless communication systems. In these cases, it cannot be foreseen which of the L channel coefficients contribute most significantly to the intersymbol interference. The present invention determines these most significant coefficients adaptively, and then processes the intersymbol interference caused by them using a tap-selectable RSSE, i.e., TS-RSSE. The present invention also adaptively processes the intersymbol interference caused by the less significant coefficients with a tap selectable DFP technique (TS-DFP). With each change of the channel impulse response, a new determination is made concerning which of the L channel coefficients associated with the memory, i.e., {fi}, 1xe2x89xa6ixe2x89xa6L, are to be adaptively selected for processing in accordance with either the TS-DFP technique or the TS-RSSE technique. It should be noted, that unlike prior art implementations the present invention does not reduce the number of states of the trellis considered by the tap selectable RSSE technique (TS-RSSE).
Accordingly, the invention provides a receiver apparatus and associated method for reducing the number of channel coefficients whose intersymbol interference is to be processed with the high complexity TS-RSSE cancellation algorithm. In a preferred embodiment, channel coefficients are adaptively selected as contributing most significantly to the intersymbol interference, and are processed by the TS-RSSE technique. The non-selected channel coefficients are processed with a TS-DFP technique.
The determination as to which channel coefficients contribute most significantly to the intersymbol interference is implemented in a number of alternate embodiments. In a first embodiment, channel coefficients are adaptively selected for processing by the TS-RSSE technique based on whether the coefficient""s squared or absolute value is above a predetermined threshold. Those coefficients exceeding the threshold will be processed by the TS-RSSE technique, and those coefficients below the threshold will be processed by the TS-DFP technique.
In a second embodiment, channel coefficients are adaptively selected for processing by the TS-RSSE technique by establishing a threshold and summing the squared or absolute value of the channel coefficients in decreasing squared or absolute value order until the threshold is met. The intersymbol interference associated with the channel coefficients which collectively sum to the threshold value are processed by the TS-RSSE technique. While the intersymbol interference associated with those coefficients not included in the summation are processed by the TS-DFP technique.
In a third embodiment, channel coefficients are adaptively selected for processing by the TS-RSSE technique by selecting only those channel coefficients whose absolute or squared value is highest. A prescribed number of coefficients may be selected for inclusion in the set.
The receiver of the present invention is referred to as a tap-selectable RSSE equalizer/decoder (TS-RSSE) with a tap-selectable decision prefilter (TS-DFP). The channel impulse response is modeled in the receiver by L+1 taps, {fi}, 0xe2x89xa6ixe2x89xa6L, (i.e., the memory is L). The first K taps associated with the channel memory, {fi}, 1xe2x89xa6ixe2x89xa6K, are referred to as non-selectable taps and are processed with a high complexity TS-RSSE cancellation algorithm. The remaining taps associated with the channel memory, {fi}, K+1xe2x89xa6ixe2x89xa6L, are referred to as selectable taps and are analyzed to adaptively select V taps to achieve a reasonably low bit error rate BER. The tap selection process is adaptive in the sense that the V taps identified in any selection period change with a changing channel environment. The intersymbol interference caused by the adaptively selected V taps are processed with the high complexity TS-RSSE cancellation algorithm. The intersymbol interference caused by the non-selected Lxe2x88x92(K+V) taps are processed with a lower complexity TS-DFP cancellation algorithm.
The adaptive TS-RSSE equalizer/decoder of the present invention advantageously reduces the complexity of a conventional RSSE equalizer/decoder (See FIG. 2) by only processing the intersymbol interference caused by a reduced number of channel coefficients with a high complexity TS-RSSE equalizer/decoder and processing the intersymbol interference caused by the remaining channel coefficients with a lower complexity TS-DFP circuit. The present invention is advantageous over the prior art RSSE equalizer/decoder in that the prior art RSSE equalizer/decoder processes the intersymbol interference due to all channel coefficients of the channel impulse response. By contrast, the present invention is of lower complexity by virtue of only processing the intersymbol interference caused by a reduced number of channel coefficients with a TS-RSSE circuit. The present invention, however, does not further change the number of states which are processed in the RSSE circuit, which facilitates the implementation in dedicated hardware and preserves the bit error rate performance of a conventional RSSE circuit. Further, the receiver of the present invention provides superior performance over a prior art reduced complexity RSSE equalizer/decoder, as illustrated in FIG. 3, in that the prior art receiver assumes that the more significant channel coefficients are located in the beginning of the channel impulse. Advantageously, the hardware increase in constructing a TS-RSSE equalizer/decoder of the present invention over a reduced complexity RSSE equalizer/decoder of the prior art, as shown in FIGS. 3 and 4 is moderate. No presumption is made apriori concerning which channel coefficients are more significant to process their associated intersymbol interference by the TS-RSSE circuit, but rather, an a posteriori determination is made in response to a changing channel impulse response.